1. Field of the Invention
The invention relates to a high speed binary counter. More particularly, the invention relates to a high speed binary counter optimized to run faster and provide higher accuracy. This is achieved through the implementation of additional flip-flops and AND gates for higher order input terms of the binary counter.
2. Description of the Prior Art
With reference to FIG. 1, a comparison of decimal to binary counting is provided. Binary counting is commonly achieved through the use of a binary counter. A binary counter is a digital circuit having a clock input and a number of count outputs that give the number of clock cycles. The output may change either on rising or falling clock edges. The circuit may also have a reset input that sets all outputs to zero when asserted. The binary counter may be either a synchronous counter or a ripple counter. In order to produce a binary counter, a system of sequential logic is implemented with a digital flip-flop for each binary bit (that is, the B0 output is implemented with one flip-flop, the B1 output is implemented with one flip-flop and so on). The sequential logic is able to count by generating the proper input value to the flip-flop to produce the desired output at the time of the clock input rising edge.
Many techniques are known for creating high speed binary counters. As those skilled in the art will appreciate, one such technique employs a D flip-flop with gate logic on the D input of the flip-flop. Another technique employs “toggle” (or T) flip-flops with gate logic on the T input of the flip-flop.
As those skilled in the art will certainly appreciate, a flip-flop is a bistable gate having two stable states. The flip-flop maintains its states indefinitely until an input pulse, called a trigger, is received. When a trigger is received, the flip-flop outputs change their states according to defined rules, and remain in those states until another trigger is received. There are several different kinds of flip-flop circuits, including, but not limited to, D and T flip-flops as employed in accordance with the present invention. Flip-flop circuits are interconnected to form the logic gates that comprise digital integrated circuits (ICs) such as memory chips and microprocessors.
With reference to FIG. 2, the first four bits of a common binary counter are shown. FIG. 2 shows the binary counter implemented through the utilization of D flip-flops. The enable, set and reset inputs of the flip-flops have been removed for illustration clarity and those skilled in the art will certainly appreciate how they function in accordance with this explanation. In the case of a counter implemented with D flip-flops, the D input is the flip-flop output exclusive ORed (XOR) with the product of all lower order outputs. For example:B3.d =B3XOR(B2 AND B1 AND B0)
For every case:Bn.d=BnXOR(B(n−1) AND B(n−2) . . . AND B0)
For the case B0, it can be shown that the inverter between the D input and the flip-flop output is equivalent to an exclusive OR gate with one input tied high (true).
The problem that limits the speed of the counter is the AND gate that grows with the number of bits of the counter and the routing problems associated with transmitting lower order bit information to the AND gates. Sixteen-bit counters are common, requiring a 15-input AND gate to implement the MSB (Most Significant Bit). 32-bit counters are not unusual in modern electronics, requiring a large number of very wide AND gates. The routing and switching delays of these gates limit the speed at which the counter can operate.
As those skilled in the art will certainly understand, the most significant bit is the bit in a multiple-bit binary number with the largest value. This is usually the bit farthest to the left in numerical representation, or the bit transmitted first in a sequence. For example, in the binary number 1000, the MSB is 1, and in the binary number 0111, the MSB is 0.
High speed binary counters implemented with toggle, or T, flip-flops suffer from the same problems. With reference to FIG. 3, the first four bits of a binary counter are shown implemented with toggle flip-flops. As in the case of the D flip-flop version, each more significant bit requires a larger AND gate. B3 requires a three-input AND gate on the Toggle input, B4 requires a four-input AND gate, and so on. As such, a 32-bit counter will require a 31-input AND gate on its MSB.
The equation for the T input may be expressed as:Bn.t=B(n−1) AND B(n−2) . . . AND B0
Those skilled in the art will appreciate the B1 and B0 inputs can also be derived from this equation.
The binary counter implemented with the T flip-flops, therefore, suffers from the same limitations as the D flip-flops discussed above. It may further be implied that any binary counter designed from any type of memory cell (whether any kind of flip-flop or other device) suffers from this same problem of incrementally larger AND gates and greater signal routing requirements as the number of bits grows.
When using a binary counter, it is advantageous to use a counter that increments in orderly binary format so a format conversion is not required. Counters are well known that count in Gray code format. These counters offer some advantage in operating speed. Ultimately, the output of these counters must be converted to binary format. This Gray code to binary conversion expends logic resources and time. A counter that can increment as rapidly as possible in true binary format is desirable.
With this in mind, FIG. 4 shows the transitions of an ideal binary counting process for the values 241 through 259. In this ideal system, there are no propagation or transport delays for the combinational logic or any transition delays for the sequential logic. All of the signals transition at exactly the same time.
FIG. 4 illustrates, however, the problem with the utilization of a large AND gate. Specifically, the 8-input AND gate that provides input to the B8 flip-flop is exemplary of the problems associated with the use of larger AND gates. There are two problems that occur in the Region of Interest indicated in FIG. 4. First, the input to the B8 flip-flop must be stable before the clock rising edge. In order to accomplish this, all of the input signals to the AND gate must be transported early enough to allow for the AND gate propagation delay and the flip-flop setup time.
Flip-flops require that the logical value on the input signal remain stable for some finite amount of time prior to the trigger pulse. If the input data changes at or close to the time of the trigger, the flip-flop may not capture the data or may become metastable. A metastable flip-flop's output may actually oscillate (change state) a few times before settling, at which point the settled output value has the same chances of assuming a logical value of 1 or 0 regardless of the input value. Therefore, insuring the proper set-up time is critical to implementing a reliable counter circuit.
All combinational logic gates require some finite amount of time to generate a valid output based on the input data. The amount of time a logic gate requires to generate a valid output is known as propagation delay. Combinational logic gates with more inputs typically cause more propagation delay. Similarly, electronic signals require some finite amount of time to travel through conductors from one part of a circuit to another. This travel time is known as transport delay. As a circuit becomes larger and more complicated the propagation delays and transport delays become greater.
The maximum speed (or frequency) at which a digital circuit can operate is influenced by the transport delays and propagation delays of the combinational logic and the set-up time of the flip-flops. If a counter operates at 100 MHz, the operational period of the counter is 1 second divided by 100,000,000, or 10 nano seconds. For a counter to operate reliably at 100 MHz, the maximum propagation delay plus the transport delay plus the set-up time must be less than 10 nano seconds (that is less than the period).
Flip-flop hold time (the time that the flip-flop input values must remain true after the trigger pulse) may also be considered in some systems, but is considered to be minimal or 0 in modern digital electronics.
The most critical input to the AND gate is the B0 output. The B0 signal has only one clock period to be routed from the output of its flip-flop to the input of the AND gate at B8. If there were only one route to account for, the routing would be trivial. The routing problem is complicated by the fact that the B0 signal must be routed to the input of every AND gate employed by the binary counter. Because of the demands of the system, one of the limitations to the speed of the counter is the worst case transport delay of the B0 signal throughout the system.
The second problem is the transition of the AND gate inputs from all logic “1”s to all “0”s. This transition requires the maximum propagation delay for some types of logic. Further, this logic transition is dependent on the transport delay of every less significant flip-flop. This means every signal route in the system becomes critical to the more significant bits. If the system is required to operate faster than the transport delays, a glitch can occur causing a false value in more significant bits. Routing delays are an important contributing factor to the speed of the counter.
In understanding the high speed binary counter of the present invention, which overcomes the limitations discussed above, two observations are important. First, the more significant bits have many clock cycles of time to be transported to the AND gate. Second, when the AND gate has all logic “1” inputs, the change of any single input is significant to change the gate output. For instance, in the FIG. 4 region of interest, if any of the B0 through B7 outputs changes to logic “0” prior to the next clock edge (also allowing for propagation delay), then the B8 flip-flop will respond properly.
With the foregoing in mind, a need exists for an improved high speed binary counter that is capable of counting faster with higher accuracy. The present invention provides such a high speed binary counter.